#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <algorithm>
#include <unordered_map>

using namespace std;

struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// 662. 二叉树最大宽度
class Solution1
{
public:
    int widthOfBinaryTree(TreeNode* root) 
    {
        vector<pair<TreeNode*, unsigned int>> q;
        q.push_back({root, 1});
        unsigned int ret = 0;

        while(!q.empty())
        {
            // 更新这一层的宽度
            auto& [x1, y1] = q[0];
            auto& [x2, y2] = q.back();
            ret = max(ret, y2 - y1 + 1);

            // 让下一层进队
            vector<pair<TreeNode*, unsigned int>> tmp;
            for(auto& [x, y] : q)
            {
                if(x->left) tmp.push_back({x->left, 2 * y});
                if(x->right) tmp.push_back({x->right, 2 * y + 1});
            }

            q = tmp;
        }        

        return ret;
    }
};

// 227. 基本计算器 II
class Solution2
{
public:
    int calculate(string s) 
    {
        vector<int> st;
        int i = 0, n = s.size();
        char op = '+';
        
        while(i < n)
        {
            if(s[i] == ' ') ++i;
            else if(s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while(i < n && s[i] >= '0' && s[i] <= '9')
                {
                    tmp = tmp * 10 + (s[i] - '0');
                    ++i;
                }

                if(op == '+') st.push_back(tmp);
                else if(op == '-') st.push_back(-tmp);
                else if(op == '*') st.back() *= tmp;
                else st.back() /= tmp;
            }
            else
            {
                op = s[i];
                ++i;
            }
        }

        int ret = 0;
        for(auto x : st) ret += x;
        return ret;
    }
};

// 394. 字符串解码
class Solution3
{
public:
    string decodeString(string s) 
    {
        stack<string> st;
        stack<int> nums;
        st.push("");
        int i = 0, n = s.size();

        while(i < n)
        {
            if(s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while(s[i] >= '0' && s[i] <= '9')
                {
                    tmp = tmp * 10 + (s[i++] - '0');
                }
                nums.push(tmp);
            }
            else if(s[i] == '[')
            {
                ++i;
                string tmp;
                while(s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i++];
                }
                st.push(tmp);
            }
            else if(s[i] == ']')
            {
                string tmp = st.top();
                st.pop();
                int k = nums.top();
                nums.pop();

                while(k--)
                {
                    st.top() += tmp;
                }
                ++i;
            }
            else
            {
                string tmp;
                while(i < n && s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i++];
                }
                st.top() += tmp;
            }
        }

        return st.top();
    }
};

// 946. 验证栈序列
class Solution4
{
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) 
    {
        stack<int> st;
        int i = 0, n = pushed.size();
        for(auto x : pushed)
        {
            st.push(x);
            while(!st.empty() && st.top() == popped[i])
            {
                st.pop();
                ++i;
            }
        }
        return i == n;
    }
};

class Node 
{
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

// 429. N 叉树的层序遍历
class Solution5
{
public:
    vector<vector<int>> levelOrder(Node* root) 
    {
        vector<vector<int>> ret;
        if(root == nullptr) return ret;
        queue<Node*> q;
        q.push(root);

        while(!q.empty())
        {
            int n = q.size();
            vector<int> tmp;
            for(int i = 0; i < n; ++i)
            {
                Node* t = q.front();
                q.pop();
                tmp.push_back(t->val);
                for(Node* child : t->children)
                {
                    if(child) q.push(child);
                }
            }

            ret.push_back(tmp);
        }

        return ret;
    }
};

// 103. 二叉树的锯齿形层序遍历
class Solution6
{
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
    {
        vector<vector<int>> ret;
        if(root == nullptr)
            return ret;
        
        queue<TreeNode*> q;
        q.push(root);
        bool isLeft = true;
        while(!q.empty())
        {
            int n = q.size();
            vector<int> tmp;
            for(int i = 0; i < n; ++i)
            {
                TreeNode* t = q.front();
                q.pop();
                tmp.push_back(t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }

            if(!isLeft)
            {
                reverse(tmp.begin(), tmp.end());
            }
            isLeft = !isLeft;
            ret.push_back(tmp);
        }

        return ret;

        return ret;
    }
};

// 515. 在每个树行中找最大值
class Solution7
{
public:
    vector<int> largestValues(TreeNode* root) 
    {
        vector<int> ret;
        if(root == nullptr) return ret;
        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty())
        {
            int n = q.size();
            int tmp = INT_MIN;
            for(int i = 0; i < n; ++i)
            {
                TreeNode* t = q.front();
                q.pop();
                tmp = max(tmp, t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            ret.push_back(tmp);
        }

        return ret;
    }
};

// 703. 数据流中的第 K 大元素
class KthLargest 
{
private:
    priority_queue<int, vector<int>, greater<int>> heap;
    int _k;

public:
    KthLargest(int k, vector<int>& nums) 
    {
        _k = k;
        for(auto x : nums)
        {
            heap.push(x);
            if(heap.size() > _k) heap.pop();
        }
    }
    
    int add(int val) 
    {
        heap.push(val);
        if(heap.size() > _k) heap.pop();
        return heap.top();
    }
};

// 692. 前K个高频单词
class Solution8
{
private:
    using PSI = pair<string, int>;

    struct cmp
    {
        bool operator()(const PSI& a, const PSI& b)
        {
            // 频次相同，字典序按照大根堆的方式排列
            if(a.second == b.second)
            {
                return a.first < b.first;
            }
            return a.second > b.second;
        }
    };

public:
    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        // 统计每个单词的频次
        unordered_map<string, int> hash;
        for(auto& s : words) ++hash[s];

        // 创建一个大小为 k 的堆
        priority_queue<PSI, vector<PSI>, cmp> heap;

        // TOPK
        for(auto& psi : hash)
        {
            heap.push(psi);
            if(heap.size() > k) heap.pop();
        }

        vector<string> ret(k);
        for(int i = k - 1; i >= 0; --i)
        {
            ret[i] = heap.top().first;
            heap.pop();
        }
        return ret;
    }
};

// 295. 数据流的中位数
class MedianFinder 
{
private:
    priority_queue<int, vector<int>, less<int>> left; // 大根堆
    priority_queue<int, vector<int>, greater<int>> right; // 小根堆

public:
    MedianFinder() 
    {}
    
    void addNum(int num) 
    {
        if(left.size() == right.size())
        {
            if(left.empty() || num <= left.top())
            {
                left.push(num);
            }
            else
            {
                right.push(num);
                left.push(right.top());
                right.pop();
            }
        }
        else
        {
            if(num <= left.top())
            {
                left.push(num);
                right.push(left.top());
                left.pop();
            }
            else
            {
                right.push(num);
            }
        }
    }
    
    double findMedian() 
    {
        if(left.size() == right.size())
            return (left.top() + right.top()) / 2.0;
        else
            return left.top();
    }
};